#!/usr/bin/env python
#encoding: latin1

def quick_sort(lista, comparador):
	"""Ordena la lista de forma recursiva"""
	_quick_sort(lista, 0, len(lista) - 1, comparador)

def _quick_sort(lista, inicio, fin, comparador):
	"""Funcion quick_sort recursiva"""
	if inicio >= fin:
		return

	menores = _partition(lista, inicio, fin, comparador)
	_quick_sort(lista, inicio, menores - 1, comparador)
	_quick_sort(lista, menores + 1, fin, comparador)

def _partition(lista, inicio, fin, comparador):
	"""Funcion partición que trabaja sobre la misma lista"""
	pivote = lista[inicio]
	menores = inicio
	
	for i in xrange(inicio + 1, fin + 1):
		if comparador(lista[i], pivote) == -1:
			menores += 1
			if i != menores:
				_swap(lista, i, menores)
	if inicio != menores:
		_swap(lista, inicio, menores)
	return menores

def _swap(lista, i, j):
	"""Intercambia los elementos i y j de lista"""
	lista[j], lista[i] = lista[i], lista[j]
		

